#include "main/utils.h"
using namespace std;

class Trie {
  private:
    vector<Trie*> children;
    bool is_end;

    Trie* searchPrefix(string word) {
      Trie* node = this;
      for (auto c : word) {
        if (node->children[c - 'a'] == nullptr) {
          return nullptr;
        }
        node = node->children[c - 'a'];
      }
      return node;
    }
  public:
    Trie() : children(26), is_end(false) {
    }

    void insert(string word) {
      Trie* node = this;
      for (auto c : word) {
        if (node->children[c - 'a'] == nullptr) {
          node->children[c - 'a'] = new Trie();
        }
        node = node->children[c - 'a'];
      }
      node->is_end = true;
    }

    bool search(string word) {
      auto node = searchPrefix(word);
      return node != nullptr && node->is_end;
    }

    bool startsWith(string prefix) {
      auto node = searchPrefix(prefix);
      return node != nullptr;
    }
};

int main() {
  Trie* node = new Trie();
  node->insert("apple");
  cout << node->search("apple") << endl;
  cout << node->search("app") << endl;
  cout << node->startsWith("app") << endl;
  node->insert("app");
  cout << node->search("app") << endl;
}
